/*
 * search.h
 *
 *  Created on: 15.03.2013
 *      Author: valya
 */

#ifndef SEARCH_H_
#define SEARCH_H_

#include <vector>

struct point_t{
	double x, y;

	point_t(double x_, double y_);

	point_t(const point_t &p);

	point_t();
};

struct rect_t
{
	point_t l, r;

	rect_t(point_t l_, point_t r_);
};

struct tree_t
{
	struct Node
	{
		struct adv_point
		{
			point_t point;
			int id;
			int left_fr, right_fr;

			adv_point(point_t p);

			adv_point(int i);
		};

		int lf, rf;
		Node *left;
		Node *right;
		std::vector<adv_point> array;

		Node(std::vector<point_t> &a);

		Node();

		~Node();
	};

	Node *root;

	tree_t(std::vector<point_t> &p);

	std::vector<point_t> search_in_rect(rect_t r);

	~tree_t();
};


#endif /* SEARCH_H_ */
